<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 用来标记计算结果
      const compare = {
        LESS_THAN: -1, // 小于
        BIGGER_THAN: 1, // 大于
        EQUALS: 0, // 等于
      };

      class minHeap {
        heap = []; // 数组结构管理数据

        // 计算方法单独封装
        compareFn(a, b) {
          if (a === b) {
            return compare.EQUALS;
          }
          return a < b ? compare.LESS_THAN : compare.BIGGER_THAN;
        }

        getLeftIndex(index) {
          return index * 2 + 1;
        }

        getRightIndex(index) {
          return index * 2 + 2;
        }

        getParentIndex(index) {
          if (index === 0) {
            return undefined;
          }
          return Math.floor((index - 1) / 2);
        }

        // 插入方法
        insert(value) {
          if (value != null) {
            this.heap.push(value);
            // 此时开始和父节点相比 如果比父节点小  交换位置
            this.shiftUp(this.heap.length - 1);
            return true;
          }
          return false;
        }

        // 从下往上逐级去比较父级节点
        shiftUp(index) {
          let parent = this.getParentIndex(index);

          // 判断父节点比子节点大  那么就交换位置
          while (
            index > 0 &&
            this.compareFn(this.heap[parent], this.heap[index]) ===
              compare.BIGGER_THAN
          ) {
            swap(this.heap, parent, index);
            index = parent; // 此时交换索引

            parent = this.getParentIndex(index);
          }
        }

        size() {
          return this.heap.length;
        }

        isEmpty() {
          return this.size() === 0;
        }
        findMinimum() {
          return this.heap[0];
        }

        /* 
        删除节点的思路
        将最后一个位置的值移动到第一个位置 然后再进行父子级之间的比较
        */
        extract() {
          if (this.isEmpty()) {
            return undefined;
          }
          if (this.size() === 1) {
            return this.heap.shift();
          }
          const removed = this.heap[0]; // 要删除的元素
          this.heap[0] = this.heap.pop(); // 最后一个位置的值移动到第一个位置
          // 触发比较方法
          this.shiftDown(0);
          return removed;
        }

        // 封装从上到下逐级比较
        shiftDown(index) {
          let current = index; // 先获取当前索引
          // 分别获取左右节点索引
          let left = this.getLeftIndex(index);
          let right = this.getRightIndex(index);

          let size = this.size();

          // 这里是重点 检测当前元素和左节点的大小 在检测和右节点的大小
          if (
            left < size &&
            this.compareFn(this.heap[current], this.heap[left]) ===
              compare.BIGGER_THAN
          ) {
            current = left; // 如果 当前比左节点大 那么交换索引
          }
          if (
            right < size &&
            this.compareFn(this.heap[current], this.heap[right]) ===
              compare.BIGGER_THAN
          ) {
            current = right; // 如果 当前(此时已经是原来左节点索引)比右节点大 那么交换索引
          }

          // 交换值
          if (index !== current) {
            swap(this.heap, index, current);
            // 递归调用 逐级比较
            this.shiftDown(current);
          }
        }
      }

      // 封装交换值位置方法
      const swap = (array, a, b) => {
        const temp = array[a]; // 临时变量存放值
        array[a] = array[b];
        array[b] = temp;
      };

      const heap = new minHeap();
      /* 
      heap.insert(1)
      heap.insert(2)
      heap.insert(3)
      heap.insert(4)
      heap.insert(5)

      heap.extract()


      heap: [2, 4, 3, 5]

      执行的顺序 
      - [1, 2, 3, 4, 5]
      - [5, 2, 3, 4]   第一次交换 5 > 2  所以2到根节点的位置
      - [2, 5, 3, 4]   第二次交换 5 > 4  3是根节点的右子节点  与3无关 所以4到5的位置
      - [2, 4, 3, 5]

         2
       5   3
      4
      */
    </script>
  </body>
</html>
